package com.dycong.common.leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 作用描述:
 * 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
 * <p>
 * 示例 :
 * <p>
 * 输入: [1,2,1,3,2,5]
 * 输出: [3,5]
 * 注意：
 * <p>
 * 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
 * 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/single-number-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author dycong
 * @date 2019/12/24 7:53
 */
public class SingleNumber_III_260 {

    // TODO: 2019/12/23 位运算符—与（&）、非（~）、或（|）、异或（^）
    // TODO: 2019/12/23 >>(向右位移) 针对二进制，转换成二进制后向右移动3位，>>>(无符号右移)  无符号右移，忽略符号位，空位都以0补齐
    public static void main(String[] args) {
        SingleNumber_III_260 singleNumber_iii_260 = new SingleNumber_III_260();
        int[] ints = new int[]{1, 2, 1, 3, 2, 5};
        int[] ints2 = new int[]{1, 2, 1, 3, 2, 5};

        System.out.println(Arrays.toString(singleNumber_iii_260.singleNumber(ints)));
        System.out.println(Arrays.toString(singleNumber_iii_260.SingleNumber0(ints2)));
    }

    public int[] singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();

        for (int num : nums) {
            if (set.contains(num)) {
                set.remove(num);
            } else {
                set.add(num);
            }
        }
        int[] res = new int[2];
        int i = 0;
        for (int num : set) {
            res[i] = num;
            i++;
        }
        return res;
    }

    /**
     * 在诸事之前，若还不了解按位异或操作符，请先了解一下按位异或操作符（Xor）的性质：
     * <p>
     * todo 如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0（这里假设a、b 只能包含 1、0 两值，但别忘了，每个比特恰好是表示零和一的。也可以这么说：真 xor 假 = 真；真 xor 真 = 假；假 xor 假 = 假）。
     * todo 满足交换律与结合律。
     * <p>
     * <p>
     * todo 通过按位异或操作符将数组中的每个数进行累加的异或操作便可以得出唯一的两个不同数的按位异或值。
     * <p>
     * 但是，数组中有两个唯一元素，而非一个，通过依次遍历对每个元素进行单一的按位异或运算肯定取不到两个不同的数。
     * 那么，如果能否将两个不同的数区分开来，分别进行按位异或运算呢？
     * <p>
     * 当然可以！不要忘了，那是两个不同的数。也就是说，其异或结果于二进制的表达上，todo 任意一个值为一的比特位便表示了两个数的不同（如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0）。
     * <p>
     * 通过表格可知，任意两值的异或结果于二进制表达上，恰好包含了两值的不同值为一的位。所以，通过取得异或结果中任意值为一的比特位，判断每个数是否含有这个位（且位上的值为一）进行 todo 分组运算（包含与不包含的关系必然将数组区分为分别包含一个唯一数的两部分，并且，两部分除去唯一数后，其剩余元素均有重复），这样便可以得到不同的两个数了。
     * <p>
     * todo 可是如何得到两个数按位异或结果的任一不同位呢？
     * todo 通过观察可以发现，如果将某一个值得取反值加一个一后，在进行按位与操作，所得位恰好为初始值的最低位为所代表得值。
     *
     * @see 计算机中正数到负数的转换过程 -i  = ~i+1
     */

    public int[] SingleNumber0(int[] nums) {
        int sign = 0;

        //取得数组中两个唯一数的按位异或结果
        for (int num : nums) {
            sign ^= num;
        }
        //获取区分两个唯一数的比特位最低位为所代表得值,用于将两个唯一的数分到两个组里
        //也可写成 sign &= -sign;

        sign &= (~sign + 1);
        int[] res = new int[2];

        for (int num : nums) {
            if ((num & sign) == sign) {
                res[0] ^= num;
            } else {
                res[1] ^= num;
            }
        }
        return res;
    }



   /* public int[] SingleNumber0(int[] nums) {
        int sign = 0;
        //取得数组中两个唯一数的按位异或结果
        for (int i = 0; i < nums.length; i++) {
            sign ^= nums[i];
        }
        //获取区分两个唯一数的比特位所代表的值
        //也可以写成：sign &= (~sign) + 1
        sign &= -sign;
        int[] result = new int[2];
        //通过标识，区分两个数组
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] & sign) == sign) {
                result[0] ^= nums[i];
            } else {
                result[1] ^= nums[i];
            }
        }
        return result;
    }*/


}
